import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-08-22
 * Time: 11:36
 */
public class BinaryTree {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;

    public TreeNode createBinaryTree() {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);

        root = node1;
        node1.left = node2;
        node1.left = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node5.right = node8;

        return root;
    }

    public TreeNode lowestCommonAncestor(TreeNode root,
                                         TreeNode p, TreeNode q) {
        //如果是空树，就没有公共祖先
        if (root == null) {
            return null;
        }
        //如果p或者q等于root，那么公共祖先一定是root
        if (root == p || root == q) {
            return root;
        }
        //如果上面两种情况都不是，那就递归在子树里面找
        TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
        TreeNode rightTree = lowestCommonAncestor(root.right, p, q);

        //左右树如果都不是null，说明pq分别在树的两侧
        //左树为空，说明pq都在右树
        //右树为空，说明pq都在左树
        if (leftTree != null && rightTree != null) {
            return root;
        } else if (leftTree == null) {
            return rightTree;
        } else {
            return leftTree;
        }
    }

    public boolean getPath(TreeNode root,
                           TreeNode node, Stack<TreeNode> stack) {
        if (root == null) {
            return false;
        }
        stack.push(root);
        if (root == node) {
            return true;
        }
        boolean leftTree = getPath(root.left, node, stack);
        if (leftTree == true) {
            return true;
        }
        boolean rightTree = getPath(root.right, node, stack);
        if (rightTree == true) {
            return true;
        }
        //如果已经走到这里了！说明左树和右数都没有找到
        //并且说明这个root应该要pop出去
        stack.pop();
        return false;
    }

    public TreeNode lowestCommonAncestor2(TreeNode root,
                                          TreeNode p, TreeNode q) {
        //如果是空树，就没有公共祖先
        if (root == null) {
            return null;
        }
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();

        getPath(root, p, stackP);
        getPath(root, q, stackQ);

        int sizeP = stackP.size();
        int sizeQ = stackQ.size();

        int size = Math.abs(sizeP - sizeQ);
        if (sizeP > sizeQ) {
            while (size != 0) {
                stackP.pop();
                size--;
            }
        } else {
            while (size != 0) {
                stackQ.pop();
                size--;
            }
        }
        while (!stackP.isEmpty() && !stackQ.isEmpty()) {
            if (stackP.peek().equals(stackQ.peek())) {
                return stackP.peek();
            }
            stackP.pop();
            stackQ.pop();
        }
        return null;
    }

    public int i = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder, int inBegin, int inEnd) {
        if (inEnd < inBegin) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[i]);
        int inorderIndex = getInorderIndex(inorder, preorder[i], inBegin, inEnd);
        i++;
        root.left = buildTree(preorder, inorder, inBegin, inorderIndex - 1);
        root.right = buildTree(preorder, inorder, inorderIndex + 1, inEnd);

        return root;
    }

    private int getInorderIndex(int[] inorder, int val, int inBegin, int inEnd) {
        for (int j = inBegin; j <= inEnd; j++) {
            if (inorder[j] == val) {
                return j;
            }
        }
        return -1;
    }

    public int[] postorder = {3, 5, 2, 7, 4, 1, 8};
    public int i2 = postorder.length - 1;

    public TreeNode buildTree2(int[] postorder, int[] inorder, int inBegin, int inEnd) {
        if (inEnd < inBegin) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[i]);
        int inorderIndex = getInorderIndex(inorder, postorder[i], inBegin, inEnd);
        i--;
        root.right = buildTree(postorder, inorder, inorderIndex + 1, inEnd);
        root.left = buildTree(postorder, inorder, inBegin, inorderIndex - 1);
        return root;
    }

    private int getInorderIndex2(int[] inorder, int val, int inBegin, int inEnd) {
        for (int j = inBegin; j <= inEnd; j++) {
            if (inorder[j] == val) {
                return j;
            }
        }
        return -1;
    }

    public String tree2str(TreeNode root) {
        if (root == null) {
            return null;
        }

        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root, stringBuilder);
        return stringBuilder.toString();
    }

    public void tree2strChild(TreeNode root, StringBuilder stringBuilder) {
        if (root == null) {
            return;
        }
        stringBuilder.append(root.val);
        if (root.left != null) {
            stringBuilder.append("(");
            tree2strChild(root.left, stringBuilder);
            stringBuilder.append(")");

        } else {
            if (root.right != null) {
                stringBuilder.append("()");
            } else {
                return;
            }
        }
        if (root.right != null) {
            stringBuilder.append("(");
            tree2strChild(root.right, stringBuilder);
            stringBuilder.append(")");
        } else {
            return;
        }
    }

    public void preOrderNor(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

    public void inOrderNor(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }

    public void postOrder(TreeNode root) {
        TreeNode prev = null;
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null || prev == top.right) {
                System.out.print(top.val + " ");
                stack.pop();
                prev = top;
            } else {
                cur = top.right;
            }
        }
    }
}
